package com.ljy.my_study.lintcode.二叉树的路径和;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.TreeNode;

/** 
* @author James
* @date 2019年2月4日 
*/
public class TestMain2 {
	public static void main(String[] args) {
		TreeNode root=TreeNodeUtil.deserialize("-10,-20,#,#,-31,#,#,#,#,-24,-5,#,#,#,#,#,#,#,#,#,#,-6,-7,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,-1,-1");
		System.out.println(binaryTreePathSum(root,-73));
	}
	
	
	
	public static List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
		if(root==null) {
			return new ArrayList<>();
		}
        List<List<Integer>> listList=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
//        listList.add(list);
        addSonNode(listList,list,0,root,target);
        Iterator<List<Integer>> it= listList.iterator();
        while(it.hasNext()) {
        	List<Integer> l=it.next();
        	int sum=0;
        	for(Integer i:l) {
        		sum+=i;
        	}
        	if(sum!=target) {
        		it.remove();
        	}
        }
        return listList;
    }
	
	public static void addSonNode(List<List<Integer>> listList,List<Integer> list,Integer sum,TreeNode node,int target) {
		if(node==null) {
			return;
		}
//		if(sum+node.val>target) {
//			return;
//		}
		list.add(node.val);
		if(node.left==null&&node.right==null) {
			listList.add(list);
			return;   
		}
		if(node.left!=null) {
			addSonNode(listList,new ArrayList<>(list),sum+node.val,node.left,target);
		}
		if(node.right!=null) {
			addSonNode(listList,new ArrayList<>(list),sum+node.val,node.right,target);
		}
		listList.remove(list);
	}
}
